1. Field of the Invention
The present invention relates to the design of cache memories within computer systems. More specifically, the present invention relates to a method and an apparatus for predicting the occurrence of hot spots in cache memories.
2. Related Art
Microprocessors use cache memories to store frequently used data closer to the computing engines. This helps to speed up applications because it takes considerably less time to access data in cache than it does to access data in main memory. Caches, however, are not without their limitations. Caches cannot be made infinitely large due to chip area and timing considerations. Typically, caches use a hashing scheme based on a target address of the data to allocate space in the cache memory for the data. Since caches are much smaller than main memory, multiple addresses in main memory will map to the same address in cache memory. The hashing scheme controls how many lines of main memory map to the same location in cache.
“Hot spots” in cache memories result from multiple blocks of data competing for the same location in cache. When a second piece of data gets allocated to the same location in cache as a first piece of data, the first piece of data is evicted from cache. If the first piece of data is subsequently requested by the application, the application typically has to wait for the first piece of data to be retrieved again from a lower level of the memory hierarchy, thus resulting in a much longer wait than if the first piece of data was still in cache.
Typically, microprocessor designers rely on multiple levels of cache to deal with this problem. However, each new level of cache is typically further away from the processing units and thus takes longer to access than the first-level cache. While these additional levels of cache help to speed up applications, they are not that effective when dealing with hot spots. Hot spots are typically small areas in the cache that are constantly being toggled between multiple sets of data. While additional levels of cache help to reduce the time needed for each lookup, they do not completely solve the problem.
In order to deal with the problem of hot spots, it is first necessary to identify which portions of a cache memory are hot spots. Since program behavior is extremely hard to predict beforehand, this identification process must take place at run time.
Hence, what is needed is a method and an apparatus that predicts the occurrence of hot spots in cache memories to facilitate reducing the effects of the hot spots.